1. Field of the Invention
The present invention relates generally to encoding of attributes in cryptographic credentials. More particularly it relates to proofs about attributes so encoded. Still more particularly, aspects of the present invention relate to so-called anonymous credential systems.
2. Description of Related Art
Cryptographic credentials are used in a variety of security and privacy-sensitive applications to enable a user or proving party (the “prover”), to prove certain information to a verifying party (the “verifier”). Such a credential is essentially a certificate generated via a cryptographic process by an issuing party (the “issuer”) who has in some manner verified the information for which the credential is issued. The issuer, who may be the verifier but is more typically a trusted third party, supplies the credential to the user who can then use the credential as verification of the information when required. Credentials might be transmitted over data communications channels to a user's receiving module, such as a personal computer or mobile phone, or can be recorded on some information storage medium such as a chip or card which is supplied to the user.
Typical applications include government or electronic ID cards which encode personal or security-sensitive information. Such a card might be inserted in some form of reader module, with communication occurring between the card reader and a processor on the card, or between the reader and a remote verifier module, to perform a cryptographic verification process. There are also numerous applications involving access to services or other resources via data communications networks such as the Internet or telecommunications networks. An exemplary system might involve a user with a laptop, a mobile phone or other data processing module in communication with a remote server via the Internet, with verification of an appropriate cryptographic credential being required before the user is permitted access to a restricted web site.
Information is certified by a cryptographic credential via an encoding process whereby the information is represented by some value or function which is encoded in the credential via a cryptographic algorithm. Cryptographic proofs can be then be made about the credential and the information it encodes for subsequent verification purposes. Preferably, a credential system will be anonymous, allowing “zero-knowledge” proofs to be made which do not reveal any other information to a verifier than that which is to be proved. The items of information certified by cryptographic credentials are referred to generally herein as “user attributes”. Such an attribute can be any item of information attributed to a user, relating, for example, to some property, quality, feature or other item belonging to, describing or otherwise associated with the user, where the “user” here may in general be a person or a module.
Various different types of attributes might be utilized in credential systems. For example, binary attributes are attributes which can either be present or not, in essence flags indicating either true or false, e.g. whether a user is a civil servant. Finite set attributes provide another example. These are finite sets of discrete attribute values where a user may realize one possible value, examples here being hair colour, city of birth, security clearance and occupation. For simplicity, the term “attribute” is used herein to mean both “attribute” and “attribute value” as the context requires. Various other attribute types are possible as discussed below. Whatever the attribute type, for many applications the number of attributes to be encoded in cryptographic credentials can be very large.
There are currently two main approaches for encoding attributes in credentials as described above. The standard approach is to designate a message mj to an attribute and set mj to the encoded attribute value. This approach uses a whole message field per attribute. In more detail, attributes are distributed over multiple attribute bases so that each attribute is encoded in its own attribute base. That is, each attribute is encoded as one exponent mj in a discrete logarithm representation gmj where g is the attribute base for that attribute.
An example of an anonymous credential system using this technique is the Camenisch-Lysyanskaya credential system which is discussed further below. This technique generates anonymous credentials by producing Camenisch-Lysyanskaya signatures on a message set including the encoded attribute values. Zero-knowledge proofs can then be made about the encoded attributes, e.g. to reveal one attribute to a verifier without revealing any others in the credential.
A common scenario is where a user wishes to prove that her credential encodes an attribute which is, or is not, a member of a given set, e.g. on a particular list of attributes, without revealing the attribute in question. For instance, a user may need to prove that her country of birth is (or is not) one of a given list of countries. A known method for doing this is to prove that the attribute encoded in the credential is either the first one, or the second one, or the third one, etc., of the attributes in the set (or conversely that the encoded attribute is not the first one, and is not the second one, and so on).